import heapq


class GreedyAlgorithm:
    @staticmethod
    def prim(graph):
        """
        最小生成树算法 - Prim算法（Minimum Spanning Tree Algorithm - Prim's Algorithm）

        参数：
        graph (list): 图的邻接矩阵表示。

        返回：
        list: 最小生成树的边列表。

        实现思路：
        1. 创建一个集合visited，用于记录已访问的节点。
        2. 创建一个优先队列min_heap，用于选择最小权重的边。
        3. 随机选择一个节点作为起始节点，将其加入visited。
        4. 将起始节点的所有相邻边加入min_heap。
        5. 当min_heap非空时，重复以下步骤：
           - 从min_heap中弹出权重最小的边，如果其连接的节点不在visited中，则将该节点加入visited，并将该节点的所有相邻边加入min_heap。
        6. 返回最小生成树的边列表。

        """

        # 步骤 1: 创建一个集合visited，用于记录已访问的节点。
        visited = set()

        # 步骤 2: 创建一个优先队列min_heap，用于选择最小权重的边。
        min_heap = []

        # 步骤 3: 随机选择一个节点作为起始节点，将其加入visited。
        start_node = 0
        visited.add(start_node)

        # 步骤 4: 将起始节点的所有相邻边加入min_heap。
        for neighbor, weight in graph[start_node]:
            heapq.heappush(min_heap, (weight, start_node, neighbor))

        edges = []

        # 步骤 5: 当min_heap非空时，重复以下步骤：
        while min_heap:
            # 步骤 5.1: 从min_heap中弹出权重最小的边
            weight, source, target = heapq.heappop(min_heap)

            # 步骤 5.2: 如果其连接的节点不在visited中，则将该节点加入visited，并将该节点的所有相邻边加入min_heap。
            if target not in visited:
                visited.add(target)
                edges.append((source, target, weight))
                for neighbor, weight in graph[target]:
                    heapq.heappush(min_heap, (weight, target, neighbor))

        # 步骤 6: 返回最小生成树的边列表。
        return edges

    @staticmethod
    def kruskal(graph):
        """
        最小生成树算法 - Kruskal算法（Minimum Spanning Tree Algorithm - Kruskal's Algorithm）

        参数：
        graph (list): 图的边列表表示，每个边包含起始节点、目标节点和权重。

        返回：
        list: 最小生成树的边列表。

        实现思路：
        1. 创建一个并查集，用于判断两个节点是否连通。
        2. 将边列表按照权重从小到大进行排序。
        3. 遍历边列表，依次加入最小生成树的边列表中：
           - 如果边的起始节点和目标节点不在同一个连通分量中，则将该边加入最小生成树的边列表，并合并起始节点和目标节点的连通分量。
        4. 返回最小生成树的边列表。

        """

        # 步骤 1: 创建一个并查集，用于判断两个节点是否连通。
        def find(parent, node):
            if parent[node] != node:
                parent[node] = find(parent, parent[node])
            return parent[node]

        def union(parent, rank, node1, node2):
            root1 = find(parent, node1)
            root2 = find(parent, node2)
            if rank[root1] < rank[root2]:
                parent[root1] = root2
            elif rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root2] = root1
                rank[root1] += 1

        # 步骤 2: 将边列表按照权重从小到大进行排序。
        sorted_edges = sorted(graph, key=lambda x: x[2])

        n = len(graph)
        parent = list(range(n))
        rank = [0] * n
        edges = []

        # 步骤 3: 遍历边列表，依次加入最小生成树的边列表中
        for edge in sorted_edges:
            node1, node2, weight = edge
            # 步骤 3.1: 如果边的起始节点和目标节点不在同一个连通分量中，则将该边加入最小生成树的边列表，并合并起始节点和目标节点的连通分量。
            if find(parent, node1) != find(parent, node2):
                edges.append(edge)
                union(parent, rank, node1, node2)

        # 步骤 4: 返回最小生成树的边列表。
        return edges

    @staticmethod
    def knapsack_problem(weights, values, capacity):
        """
        背包问题算法（Knapsack Problem Algorithm）

        参数：
        weights (list): 物品的重量列表。
        values (list): 物品的价值列表。
        capacity (int): 背包的容量。

        返回：
        int: 背包中可以放置的最大价值。

        实现思路：
        1. 创建一个元组列表items，存储物品的索引、重量和价值。
        2. 根据物品的价值密度（价值除以重量）对items进行排序，使得价值密度最高的物品排在最前面。
        3. 遍历items，尽可能将物品放入背包中：
           - 如果物品的重量小于等于剩余容量，则将该物品完全放入背包，并将对应的价值累加到总价值中。
           - 否则，将物品的一部分放入背包，以填满剩余容量，并将对应的价值按比例累加到总价值中。
        4. 返回背包中可以放置的最大价值。

        """

        # 步骤 1: 创建一个元组列表items，存储物品的索引、重量和价值。
        items = [(i, weights[i], values[i]) for i in range(len(weights))]

        # 步骤 2: 根据物品的价值密度（价值除以重量）对items进行排序，使得价值密度最高的物品排在最前面。
        items.sort(key=lambda x: x[2] / x[1], reverse=True)

        total_value = 0
        remaining_capacity = capacity

        # 步骤 3: 遍历items，尽可能将物品放入背包中
        for item in items:
            index, weight, value = item
            # 步骤 3.1: 如果物品的重量小于等于剩余容量，则将该物品完全放入背包，并将对应的价值累加到总价值中。
            if weight <= remaining_capacity:
                total_value += value
                remaining_capacity -= weight
            else:
                # 步骤 3.2: 否则，将物品的一部分放入背包，以填满剩余容量，并将对应的价值按比例累加到总价值中。
                fraction = remaining_capacity / weight
                total_value += value * fraction
                break

        # 步骤 4: 返回背包中可以放置的最大价值。
        return total_value

    @staticmethod
    def dijkstra(graph, start):
        """
        最短路径算法 - Dijkstra算法（Shortest Path Algorithm - Dijkstra's Algorithm）

        参数：
        graph (list): 图的邻接矩阵表示。
        start (int): 起始节点。

        返回：
        list: 起始节点到其他节点的最短路径长度列表。

        实现思路：
        1. 创建一个集合visited，用于记录已访问的节点。
        2. 创建一个列表distances，用于存储起始节点到每个节点的最短路径长度，初始化为无穷大。
        3. 将起始节点到自身的距离设置为0。
        4. 当visited中的节点数小于总节点数时，重复以下步骤：
           - 从distances中选择当前距离最小的节点u，将其加入visited。
           - 遍历图中与节点u相邻的节点v，更新起始节点到节点v的最短路径长度：
             - 如果起始节点到节点v的距离大于起始节点到节点u再到节点v的距离，则更新距离。
        5. 返回起始节点到其他节点的最短路径长度列表distances。

        """

        # 步骤 1: 创建一个集合visited，用于记录已访问的节点。
        visited = set()

        # 步骤 2: 创建一个列表distances，用于存储起始节点到每个节点的最短路径长度，初始化为无穷大。
        distances = [float('inf')] * len(graph)

        # 步骤 3: 将起始节点到自身的距离设置为0。
        distances[start] = 0

        # 步骤 4: 当visited中的节点数小于总节点数时，重复以下步骤：
        while len(visited) < len(graph):
            # 步骤 4.1: 从distances中选择当前距离最小的节点u，将其加入visited。
            min_distance = float('inf')
            min_node = -1
            for node in range(len(graph)):
                if node not in visited and distances[node] < min_distance:
                    min_distance = distances[node]
                    min_node = node
            visited.add(min_node)

            # 步骤 4.2: 遍历图中与节点u相邻的节点v，更新起始节点到节点v的最短路径长度
            for neighbor in range(len(graph)):
                if (
                    neighbor not in visited
                    and graph[min_node][neighbor] > 0
                    and distances[neighbor] > distances[min_node] + graph[min_node][neighbor]
                ):
                    distances[neighbor] = distances[min_node] + graph[min_node][neighbor]

        # 步骤 5: 返回起始节点到其他节点的最短路径长度列表distances。
        return distances

    @staticmethod
    def assign_cookies(g, s):
        """
        分配饼干算法

        参数:
        g (List[int]): 孩子的胃口列表
        s (List[int]): 饼干的尺寸列表

        返回:
        int: 可以满足的孩子的数量

        实现步骤:
        1. 对孩子的胃口列表g和饼干的尺寸列表s进行排序
        2. 使用贪心策略，从胃口最小的孩子和尺寸最小的饼干开始匹配
        3. 如果当前饼干可以满足当前孩子，将孩子数量加1，并继续向后匹配
        4. 返回可以满足的孩子的数量

        """

        # 步骤 1: 对孩子的胃口列表g和饼干的尺寸列表s进行排序
        g.sort()
        s.sort()

        # 步骤 2: 使用贪心策略，从胃口最小的孩子和尺寸最小的饼干开始匹配
        child_count = 0
        cookie_count = 0

        # 步骤 3: 如果当前饼干可以满足当前孩子，将孩子数量加1，并继续向后匹配
        while child_count < len(g) and cookie_count < len(s):
            if g[child_count] <= s[cookie_count]:
                child_count += 1
            cookie_count += 1

        # 步骤 4: 返回可以满足的孩子的数量
        return child_count

    @staticmethod
    def max_profit(prices):
        """
        买卖股票的最佳时机算法

        参数:
        prices (List[int]): 股票价格列表

        返回:
        int: 可以获得的最大利润

        实现步骤:
        1. 定义最小价格和最大利润
        2. 遍历股票价格列表，更新最小价格和最大利润
        3. 返回最大利润

        """

        # 步骤 1: 定义最小价格和最大利润
        min_price = float('inf')
        max_profit = 0

        # 步骤 2: 遍历股票价格列表，更新最小价格和最大利润
        for price in prices:
            # 更新最小价格
            min_price = min(min_price, price)
            # 更新最大利润
            max_profit = max(max_profit, price - min_price)

        # 步骤 3: 返回最大利润
        return max_profit


if __name__ == '__main__':
    # 示例调用最小生成树算法 - Prim算法
    graph_prim = [
        [(1, 2), (3, 1)],
        [(0, 2), (2, 3), (3, 2)],
        [(1, 3), (4, 10)],
        [(0, 1), (1, 2), (4, 7)],
        [(2, 10), (3, 7)]
    ]
    minimum_spanning_tree_prim = GreedyAlgorithm.prim(graph_prim)
    print("最小生成树的边列表(Prim算法):", minimum_spanning_tree_prim)
    # 最小生成树的边列表(Prim算法): [(0, 3, 1), (0, 1, 2), (1, 2, 3), (3, 4, 7)]

    # 示例调用最小生成树算法 - Kruskal算法
    graph_kruskal = [
        (0, 1, 2),
        (0, 3, 1),
        (1, 2, 3),
        (1, 3, 2),
        (2, 4, 10),
        (3, 4, 7)
    ]
    minimum_spanning_tree_kruskal = GreedyAlgorithm.kruskal(graph_kruskal)
    print("最小生成树的边列表(Kruskal算法):", minimum_spanning_tree_kruskal)
    # 最小生成树的边列表(Kruskal算法): [(0, 3, 1), (0, 1, 2), (1, 2, 3), (3, 4, 7)]

    # 示例调用背包问题算法
    weights = [1, 2, 3]
    values = [6, 10, 12]
    capacity = 5
    max_value = GreedyAlgorithm.knapsack_problem(weights, values, capacity)
    print("背包中可以放置的最大价值:", max_value)
    # 输出: 背包中可以放置的最大价值: 24

    # 示例调用最短路径算法 - Dijkstra算法
    graph_dijkstra = [
        [0, 2, float('inf'), 1],
        [float('inf'), 0, 2, float('inf')],
        [3, float('inf'), 0, float('inf')],
        [float('inf'), 4, 2, 0]
    ]
    start_node = 0
    shortest_distances = GreedyAlgorithm.dijkstra(graph_dijkstra, start_node)
    print("起始节点到其他节点的最短路径长度列表:", shortest_distances)
    # 输出: 起始节点到其他节点的最短路径长度列表: [0, 2, 3, 1]

    # 示例调用分配饼干算法
    g = [1, 2, 3]
    s = [1, 1]
    assign_cookies_result = GreedyAlgorithm.assign_cookies(g, s)
    print("分配饼干算法结果:", assign_cookies_result)
    # 输出: 分配饼干算法结果: 1

    # 示例调用买卖股票的最佳时机算法
    prices = [7, 1, 5, 3, 6, 4]
    max_profit_result = GreedyAlgorithm.max_profit(prices)
    print("买卖股票的最佳时机算法结果:", max_profit_result)
    # 输出: 买卖股票的最佳时机算法结果: 5
